/*
 * Graph_test.h
 *
 *  Created on: Mar 8, 2017
 *      Author: along
 */

#ifndef GRAPH_TEST_H_
#define GRAPH_TEST_H_

#include "Result.h"
#include "Graph.h"
#include "MincostMaxflow.h"
#include "my_io.h"
#include "SaveInMap.h"
#include "AntSystem.h"
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <utility>
#include <stdexcept>
#include <algorithm>

using namespace std;

class Deployment
{
  private:
    int networknode_num, edge_networknode_num, consumer_num, cost_server;
    int s, t;
    int cost_min;
    int need_sum;
    int server_num_staic;
    Graph g_from_data;
    vector<Consumer> consumers;
    string result;
    SaveInMap avoid_dict;
    AntSystem antsystem;

  public:
    void buildGraph(char *topo[MAX_EDGE_NUM], int line_num)
    {
        // PRINTF("building graph from data...\n");
        int n, m, k, cost_s;
        sscanf(topo[0], "%d%d%d", &n, &m, &k);
        sscanf(topo[2], "%d", &cost_s);

        srand(time(NULL));
        networknode_num = n;
        edge_networknode_num = m;
        consumer_num = k;
        cost_server = cost_s;
        consumers.resize(k);
        cost_min = consumer_num * cost_server;
        server_num_staic = consumer_num;
        avoid_dict = SaveInMap(networknode_num);
        antsystem = AntSystem(networknode_num);

        // PRINTF("networknode_num: %d\t edge_networknode_num: %d\t consumer_num: %d\t cost_server: %d\n",
        //        networknode_num, edge_networknode_num, consumer_num, cost_server);

        Graph g(n + k + 2);
        s = n + k;
        t = n + k + 1;
        for (int i = 0; i < m; ++i)
        {
            int from, to, cap, cost;
            sscanf(topo[4 + i], "%d%d%d%d", &from, &to, &cap, &cost);
            Edge e = Edge(from, to, cap, cost);
            // PRINTF("edge %d :from %d to %d , cap: %d ,cost: %d\n", i, e.from, e.to, e.cap, e.cost);
            g.insert_edge(e);
#ifndef _TEST_MCMF
            e = Edge(to, from, cap, cost);
            g.insert_edge(e);
#endif
        }
        need_sum = 0;
        for (int i = 0; i < k; ++i)
        {
            int consumer_id, network_node, id_g, need;
            sscanf(topo[5 + m + i], "%d%d%d", &consumer_id, &network_node, &need);
            // PRINTF("Consumer %d: id %d , network_node: %d , need: %d\n", i, consumer_id, network_node, need);
            id_g = i + n;
            need_sum += need;
            consumers[i] = Consumer(consumer_id, network_node, id_g, need);

            Edge e = Edge(network_node, id_g, need, 0);
            g.insert_edge(e);
            e = Edge(id_g, t, need, 0);
            g.insert_edge(e);
        }
        g_from_data = g;
        upper_bound_deployment();
        inspire_deployment();
        PRINTF("ANT\n");
        antsystem_deployment();
    }

    int estimate_deloyment(Graph &g, int server_num, int *flow)
    {
        MincostMaxflow console = MincostMaxflow(g);
        int cost = console.calculate(s, t, g, flow) + cost_server * server_num;
        // PRINTF("result :f %d c %d\n", *flow, cost);
        return cost;
    }

    int estimate_deloyment(Graph &g, int *flow)
    {
        MincostMaxflow console = MincostMaxflow(g);
        int cost = console.calculate(s, t, g, flow);
        vector<Edge> e = g.get_edges(s);
        int len = e.size(), server_num = 0;
        for (int i = 0; i < len; ++i)
        {
            if (e[i].flow > 0)
            {
                ++server_num;
            }
        }
        server_num_staic = server_num;
        // PRINTF("result :f %d c %d\n", *flow, cost);
        cost += server_num * cost_server;
        return cost;
    }

    int estimate_deloyment(Graph &g, int server_num)
    {
        int flow;
        return estimate_deloyment(g, server_num, &flow);
    }

    string get_roads_from_deployment(Graph &g)
    {
        Result ret = Result(g, consumers);
        ret.resole(s, t);
        return ret.tostring();
    }

    void update_result(int cost, string ret)
    {
        cost_min = cost;
        result = ret;
        printf("need_sum:%d\tbest_cost:%d\ts_n:%d\n", need_sum, cost,server_num_staic);
    }

    string get_result()
    {
        return result;
    }

    vector<int> get_key_from_deployment(Graph &g)
    {
        vector<int> key(networknode_num,0);
        vector<Edge> e = g.get_edges(s);
        int len = e.size();
        for(int i = 0;i < len;++i)
        {
            if(e[i].cap == 0)
            {
                key[e[i].to] = -1;
            }
            else if(e[i].flow > 0)
            {
                key[e[i].to] = 1;
            }
        }
        return key;
    }

    Graph get_deployment_form_key(vector<int> &key)
    {
        Graph g = g_from_data;
        for (int i = 0; i < networknode_num; ++i)
        {
            if(key[i] == 1)
            {
                g.insert_edge(Edge(s, i, INF, 0));
            }
        }
        return g;
    }

    int check_key(vector<int> key)
    {
        State state = avoid_dict.FindStateInMap(key);
        Graph g;
        if(state.cost == -1 || state.flow == -1)
        {
            g = get_deployment_form_key(key);
            int flow,cost;
            cost = estimate_deloyment(g, &flow);
            avoid_dict.InsertStateToMap(key,State(flow,cost));
            state.flow = flow;
            state.cost = cost;
            if (state.flow == need_sum)
            {
                if (state.cost < cost_min)
                {
                    update_result(state.cost, get_roads_from_deployment(g));
                }
                return antsystem.update_with_state(key,state.cost);
            }
            return 0;
        }
        return 0;
    }

    int check_deployment(Graph &g)
    {
        int flow, cost;
        vector<int> key = get_key_from_deployment(g);
        State state = avoid_dict.FindStateInMap(key);
        if(state.cost == -1 || state.flow == -1)
        {
            cost = estimate_deloyment(g, &flow);
            avoid_dict.InsertStateToMap(key,State(flow,cost));
            if (flow == need_sum)
            {
                if (cost < cost_min)
                {
                    update_result(cost, get_roads_from_deployment(g));
                }
                antsystem.update_with_state(key,cost);
            }
            key = get_key_from_deployment(g);
            state = avoid_dict.FindStateInMap(key);
            if(state.cost == -1 || state.flow == -1)
            {
                avoid_dict.InsertStateToMap(key,State(flow,cost));
                antsystem.update_with_state(key,cost);
            }
            state = State(flow,cost);
        }
        if (state.flow == need_sum)
        {
            return state.cost;
        }
        return -1;
    }

    int shut_min_flow_server(Graph &g, int k)
    {
        vector<Edge> e = g.get_edges(s);
        int len = e.size();
        int min_flow = INF, min_pos = -1;
        for (int i = 0; i < len; ++i)
        {
            if (e[i].flow > 0)
            {
                if (e[i].flow < min_flow)
                {
                    min_flow = e[i].flow;
                    min_pos = i;
                }
            }
        }
        if (min_pos == -1)
        {
            return -1;
        }
        int cnt = 0;
        for (int i = 0; i < len; ++i)
        {
            if (e[i].flow == min_flow)
            {
                ++cnt;
                if (cnt == k)
                {
                    Edge e_t(s, e[i].to, 0, 0);
                    g.insert_edge(e_t);
                    return i;
                }
            }
        }
        if (cnt < k)
            return -1;
        return -1;
    }

    void antsystem_deployment()
    {
        while(1)
        {
            if(((float)clock())/CLOCKS_PER_SEC>TIME_LIMIT) break;
            vector<int> key = antsystem.new_state();
            // if(check_key(key) == -1) break;
            if(check_key(key) == -1) antsystem.refresh();
        }
    }

    void upper_bound_deployment()
    {
        // PRINTF("applying upper bound deployment\n");
        Graph g = g_from_data;
        for (int i = 0; i < consumer_num; ++i)
        {
            Consumer c_node = consumers[i];
            Edge e = Edge(s, c_node.network_node, INF, 0);
            g.insert_edge(e);
        }
        int flow;
        int cost = estimate_deloyment(g, consumer_num, &flow);
        if (flow == need_sum)
        {
            update_result(cost, get_roads_from_deployment(g));
        }
    }

    void inspire_deployment()
    {
        Graph g_cur = g_from_data, g_t, g_child_best;
        int k, cost, cost_child_min;
        for (int i = 0; i < networknode_num; ++i)
        {
            g_cur.insert_edge(Edge(s, i, INF, 0));
        }
        check_deployment(g_cur);
        while (1)
        {
            if (((float)clock())/CLOCKS_PER_SEC > TIME_LIMIT)
                break;
            k = 1, cost_child_min = INF;
            while (1)
            {
                g_t = g_cur;
                if (((float)clock()) / CLOCKS_PER_SEC > TIME_LIMIT)
                    break;
                if (shut_min_flow_server(g_t, k) != -1)
                {
                    cost = check_deployment(g_t);
                    if (cost != -1 && cost < cost_child_min)
                    {
                        g_child_best = g_t;
                        cost_child_min = cost;
                    }
                    ++k;
                }
                else
                {
                    break;
                }
            }
            if (cost_child_min == INF)
            {
                break;
            }
            g_cur = g_child_best;
        }
    }
};

#endif /* GRAPH_TEST_H_ */